﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics.Contracts;

namespace DataStructure.Interview
{
    public class Question4
    {
        /// <summary>
        /// assume s, t only contains ascii
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public static bool Anagram(string s, string t)
        {
            if(s == null || t == null) return false;
            if(s.Length != t.Length) return false;
            Dictionary<int, int> asciis = new Dictionary<int, int>();
            for (int i = 'a'; i < 'z' + 1; i++)
            {
                asciis.Add(i, 0);
            }
            int s_unique_count = 0;
            int t_unique_count = 0;

            foreach (char c in s)
            {
                if (asciis[c] == 0) 
                    s_unique_count++;
                asciis[c]++;
            }

            for (int i = 0; i < t.Length; i++)
			{
			 
			    char c = t[i];
                if (asciis[c] == 0)
                    return false;

                asciis[c]--;

                if (asciis[c] == 0)
                {
                    t_unique_count++;
                    if (s_unique_count == t_unique_count)
                        return t.Length == (i + 1);

                }
            }

            return false;
        }

    }
}
